Reliable data transmission is very important for wireless communication systems. Turbo codes, originally described by Berrou et al. “Near Shannon limit error-correcting coding and decoding Turbo codes,” Proc. 1993 Int. Conf. on Comm., pp. 1064-1070, which is incorporated herein by reference, can achieve a channel capacity near the Shannon Limit with sufficient Signal to Noise Ratio (SNR); also see U.S. Pat. No. 6,598,204 B1, “System and Method of Turbo Decoding” to Giese et al., issued on Jul. 22, 2003, and U.S. Pat. No. 6,516,444 B1, “Turbo-Code decoder” to Maru, issued on Feb. 4, 2003, each of which is incorporated herein by reference.
Decoding of Turbo codes is performed in an iterative way: the information processed by one decoder is fed into another decoder iteratively until a certain degree of convergence is achieved. Decoding within each decoder can be performed in several ways. Maximum A Posteriori (MAP) decoding based on the BCJR algorithm, proposed by Bahl et al., “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. On Inf. Theory, pp. 284-287, March 1974, which is incorporated herein by reference, is widely used. BCJR decoding is done according to a trellis chart, by mapping the status of convolutional memory at time k to its states at time k. As a posteriori probability (APP) is used as the probability metric for the trellis, the BCJR algorithm is generally referred to as the Maximum A Posteriori method.
In practice, the a posteriori probability may be computed in terms of the log domain value, in order to reduce complexity. Such an algorithm is referred to as the log-MAP algorithm. In an effort to reduce the decoding complexity of the BCJR algorithm, the log-MAP algorithm utilizes a suboptimum realization of the BCJR algorithm, using log-likelihood ratios and some approximations to avoid calculating the actual probabilities, and simplify some computations, for example by omitting some insignificant computations in the BCJR algorithm to reduce the complexity. These approximation algorithms indeed have smaller complexity than the BCJR algorithm, though, their error performance is not as good as that of the BCJR algorithm. Furthermore, the construction of the entire trellis diagram is still necessary in these methods.
A further simplified log-MAP algorithm is referred to as the Max log-MAP algorithm. In log-MAP algorithm, a log summation of exponentiation operations, In
            ∑      j        ⁢          ⅇ      j        ,is calculated during extrinsic information update. The exponentiation enhances the differences between individual values in the log summation. Hence, one term will dominate the log sum, which suggests the approximation
      ln    ⁢                  ∑        j            ⁢              ⅇ                  a          j                      ≈            max      j        ⁢                  (                  a          j                )            .      The log-MAP algorithm with this approximation is referred to as the Max log-Map algorithm. Thus, Max log-Map is much simpler than log-MAP, but at the expense of performance degradation.
The objective of the MAP algorithm is to obtain a good guess of bit information probabilities. These probabilities include systematic information, intrinsic information and extrinsic information. The extrinsic information is used by another decoder in the next iteration. After a certain number of iterations, the result of extrinsic information converges and the iterative process stops. The performance of Turbo decoder based on the MAP algorithm is close to the Shannon limit.
Although the performance of Turbo codes is near optimal, integrated circuit implementation of the MAP algorithm faces two main challenges: latency and memory requirement. Upon receiving a data frame, the MAP decoder works in an iterative way. In each iteration, the MAP decoder accesses the data frame and the extrinsic information generated in the previous iteration from head to tail (forward recursion) and then from tail to head (backward recursion) to collect decoding information. Based on the collected information, the decoder estimates the most likely input data. The estimation of extrinsic information is fed back to another decoder in the next iteration. This means that, for each iteration, the MAP decoder must process the data from the beginning of the data frame to the end, and then process in the reverse direction before the estimation of the extrinsic information will be made. For a data frame of n bits, the process of getting the extrinsic information takes 2n steps, and the estimation needs n steps. Hence, latency of the MAP algorithm is large. The MAP decoder has to keep all of the decoding information until the extrinsic information is generated, and the extrinsic information must be stored for the next iteration. For a data frame of n samples and a turbo code space of S, 2×n×S memory units are required to store the temporary information. For example, S=8, n=20730 in the turbo codes of the cdma2000 system, 331680 memory units are required for the MAP decoder.
It is desirable to provide a method to reduce the memory requirement and speed up the calculation in the MAP decoder.